package com.pd.ds.tree;

import java.io.Serializable;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BSTree<T extends Comparable<T>, V extends Serializable> {

	private Node<T, V> root;
	private long size;

	public void put(T key, V value) {

		Node<T, V> newNode = new Node<T, V>(key, value);
		if (root == null) {
			root = newNode;
		} else {
			put(root, newNode);
		}
		size++;
	}

	private void put(Node<T, V> parent, Node<T, V> newNode) {

		int comp = newNode.getKey().compareTo(parent.getKey());
		if (comp <= 0) {
			if (parent.getLeft() == null) {
				parent.setLeft(newNode);
			} else {
				put(parent.getLeft(), newNode);
			}
		} else {
			if (null == parent.getRight()) {
				parent.setRight(newNode);
			} else {
				put(parent.getRight(), newNode);
			}
		}
	}

	public static void main(String[] args) {
		BSTree<String, String> bst = new BSTree<String, String>();
		String[] data = { "A", "X", "Y", "D", "E", "F", "G" };
		for (String x : data) {
			bst.put(x, x);
		}
		System.out.println(bst.bfs());
		System.out.println(bst.findLargest());
		System.out.println(bst.findSecondLargest());
	}

	public V findLargest() {
		return findLargest(root);
	}

	public V findSecondLargest() {
		Node<T, V> parent = this.root;
		Node<T, V> rChild = null;
		if (size < 2) {
			throw new RuntimeException("Not enough elements.");
		}
		if (null == parent.getRight()) {
			return findLargest(parent.getLeft());
		} else {
			rChild = parent.getRight();
			while (rChild != null) {
				if (null == rChild.getRight()) {
					break;
				}
				parent = rChild;
				rChild = rChild.getRight();
			}
			return parent.getData();
		}
	}

	private V findLargest(Node<T, V> root) {

		if (null != root) {
			V largest = findLargest(root.getRight());
			if (null == largest) {
				return root.getData();
			} else {
				return largest;
			}
		} else {
			return null;
		}
	}

	public List<V> bfs() {
		Queue<Node<T, V>> queue = new LinkedList<BSTree<T, V>.Node<T, V>>();

		Node<T, V> temp = root;
		queue.add(temp);

		List<V> values = new LinkedList<V>();
		while (queue.peek() != null) {

			temp = queue.poll();
			values.add(temp.getData());
			if (null != temp.getLeft()) {
				queue.add(temp.getLeft());
			}
			if (null != temp.getRight()) {
				queue.add(temp.getRight());
			}
		}
		return values;

	}

	public V get(T key) {

		Node<T, V> temp = root;
		if (temp != null) {
			int comp = key.compareTo((T) temp.getKey());
			if (comp == 0)
				return (V) temp.getData();
			else if (comp < 0)
				temp = temp.left;
			else
				temp = temp.right;
		}
		return null;
	}

	private class Node<T, V> {
		T key;
		V data;

		Node<T, V> right, left;

		public Node(T key, V data) {
			super();
			this.key = key;
			this.data = data;
		}

		public T getKey() {
			return key;
		}

		public V getData() {
			return data;
		}

		public Node<T, V> getRight() {
			return right;
		}

		public void setRight(Node<T, V> right) {
			this.right = right;
		}

		public Node<T, V> getLeft() {
			return left;
		}

		public void setLeft(Node<T, V> left) {
			this.left = left;
		}

	}
}